package leetcode_61_80;

public class climbStairs_70 {
    /**
     * n 阶才能到达楼顶。
     * 每次可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        /**
         * 递归解决即可
         * 这样竟然超时了
         */
        if(n==0)
            return 1;
        else if(n==1)
            return 1;
        return climbStairs(n-1)+climbStairs(n-2);
    }


    public int climbStairs2(int n) {
        /**
         * 思考了一下，可以采用动态规划
         * 爬到第 x 级台阶的方案数是爬到第x−1 级台阶的方案数和爬到第x−2 级台阶的方案数的和
         */
        int x_1=1,x_2=1,x_n=1;  //都初始化1
        for(int i=2;i<=n;i++){  //从2开始
            x_n=x_1+x_2;
            x_2=x_1;       //更新前一个和前两个
            x_1=x_n;
        }
        return x_n;
    }
}
